package org.example.flashback;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 力扣回溯算法
 * @Author chaigq
 * @Date 2020/11/26 上午7:01
 * @Version 1.0
 */
public class LeetCodeBack {
    // TODO 回溯算法
    // 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
    // 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，
    // 这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，
    // 有“通用解题方法”的美称。
    // 2.使用方法
    //回溯我认为也就是一种递归，有以下四个参数（前三个是必须的最后一个可以没有可以多个），当然不一定是我所举例的类型，要看题目而定
    // TODO 一个全局变量集合保存所有满足条件的答案，举例：List<List<Integer>> list
    //一个集合保存一个满足条件的答案，举例：List<Integer> tempList
    //算法问题给所给的输入条件，这个可能是一个字符串，也可能是一个数组
    //附加参数（可有可无，视题目而定）也可以多个
    //
    //1.出口
    //回溯法用到的核心思想就是递归，而一个递归算法一定会有一个函数出口，否则就会死循环。而出口语句该如何写很简单，
    // 难得在于出口语句该放在函数的哪个位置。关于出口条件，代码比较简单，但是位置比较重要。总结了以往所做的一些题后，
    // 发现一个万能规律，那就是把出口语句放在递归函数的第一行就行。
    //2.递归函数的参数
    //般情况下，递归函数是要带参数的，因为递归操作都是要用来处理下一次的过程，如果没有参数的话，那么就很那从下一次的操作回溯到当前操作了。
    //这个参数是随着每一次的递归操作而发生改变的。而回溯法很关键的一点就是：如果当前操作行不通，如何回溯到上一步操作。
    //既然参数会发生改变，那么我们要如何保存其上一步操作的值呢？
    //做法很简单就是不破坏当前参数的值，直接把当前值加上一个值(大家可以理解为定义了另一个非当前值的值给传到下一次函数)，只要不破坏当前值，函数就能回溯。
    //除此以外，就是结果一定是要有一个全局参数来保存，这个全局参数不会随着每一次的递归操作而随时改变，它只是用来保存每一次递归操作成功时的结果，其它的不关它的事。
    //3.递归函数的处理逻辑
    //这个过程是最关键的了，但是也很少有人能把它说清楚，当然也包括我。我想来想去，总结就是：
    //如果当前递归过程的处理参数符合要求，则（1）执行相关赋值或其它操作，
    // （2）然后转入下一次递归； 如果下一次递归不能找到出口，则把之前相关赋值或其它操作重置为初始状态。
    //如果当前路径不正确，回退时一定要把之前改变的状态还原回去，否则会导致回退后的新路径不能遍历所有可能。
    //
    //3注意事项
    //1、函数被调用返回时，返回到调用它的下一条语句
    //2、递归也是如此，递归调用时返回到上一次递归调用的下一条汇编语句
    //3、递归调用时，每个递归函数都有自己的一个栈帧，数据互不影响
    //4、递归调用时没有被执行到的语句（也就是递归返回语句）还是递归调用前的状态
    //5、回溯算法相当于层层递归，等到递归返回时，对数据的所有操作全部为初始状态 比如声明了一个全局变量vector v;回溯之后v的大小还是0
    //6、递归调用之前的语句是对全局数据或者局部数据的操作
    //7、递归调用之后的语句是对全局数据或者局部数据的恢复
    //8、全局数据一定要恢复，因为只有递归调用从始至终只有一块存储空间。
    //9、局部数据如果操作(改变时：a+1 a没有改变，++a a才改变)是在递归函数参数上，也要进行恢复
    //10、有改变就一定要恢复

    /**
     * 括号
     * 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
     *
     * 说明：解集不能包含重复的子集。
     * 例如，给出 n = 3，生成结果为：
     * [
     *   "((()))",
     *   "(()())",
     *   "(())()",
     *   "()(())",
     *   "()()()"
     * ]
     *
     */
    List<String> list = new ArrayList<>();
    public List<String> generateParenthesis(int n) {

        // 左括号个数
        int left = n;
        // 右括号个数
        int right = n;
        generateParenthesisDfs(left, right, "", n);
        return list;
    }

    private void generateParenthesisDfs(int left, int right, String s, int n) {
        if (s.length() == 2 * n) {
            list.add(s);
            return;
        }
        //约束条件
        // 只要(有剩，就可以选(。 (((((这么选，都还不能判为非法。
        //当)剩下的比(多时，才可以选)，否则，)不能选，选了就非法了。

        // 选(
        if (left > 0) generateParenthesisDfs(left - 1, right, s + "(", n);
        // 选)
        if (right > left) generateParenthesisDfs(left, right - 1, s + ")", n);
    }
    // =============================================================================
    public List<String> generateParenthesis2(int n) {

        // 左括号个数
        int left = 0;
        // 右括号个数
        int right = 0;
        generateParenthesisDfs(left, right, "", n);
        return list;
    }

    private void generateParenthesisDfs2(int left, int right, String s, int n) {
        if (s.length() == 2 * n) {
            list.add(s);
            return;
        }

        // 如果左括号小于n，即还可以添加左括号
        if (left <= n) generateParenthesisDfs(left + 1, right, s + "(", n);
        // 如果右括号小于左括号(必须如此，这样的括号才是有效的)
        if (right < left) generateParenthesisDfs(left, right + 1, s + ")", n);
    }

    /**
     * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
     *
     *  单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     *
     *  示例:
     *  board =
     * [
     *   ['A','B','C','E'],
     *   ['S','F','C','S'],
     *   ['A','D','E','E']
     * ]
     *
     * 给定 word = "ABCCED", 返回 true
     * 给定 word = "SEE", 返回 true
     * 给定 word = "ABCB", 返回 false
     *
     *  提示：
     *  board 和 word 中只包含大写和小写英文字母。
     *  1 <= board.length <= 200
     *  1 <= board[i].length <= 200
     *  1 <= word.length <= 10^3
     *
     *  Related Topics 数组 回溯算法
     */
    // 整体思路
    //使用深度优先搜索（DFS）和回溯的思想实现。关于判断元素是否使用过，我用了一个二维数组 mark 对使用过的元素做标记。
    //
    //外层：遍历
    //首先遍历 board 的所有元素，先找到和 word 第一个字母相同的元素，然后进入递归流程。假设这个元素的坐标为 (i, j)，进入递归流程前，先记得把该元素打上使用过的标记：
    //
    //mark[i][j] = 1
    //内层：递归
    //好了，打完标记了，现在我们进入了递归流程。递归流程主要做了这么几件事：
    //
    //从 (i, j) 出发，朝它的上下左右试探，看看它周边的这四个元素是否能匹配 word 的下一个字母
    //如果匹配到了：带着该元素继续进入下一个递归
    //如果都匹配不到：返回 False
    //当 word 的所有字母都完成匹配后，整个流程返回 True
    //几个注意点
    //递归时元素的坐标是否超过边界
    //回溯标记 mark[i][j] = 0以及 return 的时机
    //
    public boolean exist(char[][] board, String word) {
        // 将字符串转换成数组
        char[] words = word.toCharArray();
        // 遍历二维矩形结构
        for (int i = 0; i < board.length; i++) {
            // 列遍历
            for (int j = 0; j < board[0].length; j++) {
                if (existDfs(i, j, words, board, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean existDfs(int i, int j, char[] words, char[][] board, int index) {
        // 判断当前节点边界，上下左右
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[index]){
            return false;
        }
        // 当word的全部字符都遍历完后
        if (index == words.length - 1){
            return true;
        }
        // 修改当前节点值
        char temp = board[i][j]; // 保存当前节点值
        board[i][j] = '/';      // 修改节点值
        // 从上下左右四个方向走
        boolean bool = existDfs(i - 1, j, words, board, index + 1) ||
                       existDfs(i + 1, j, words, board, index + 1) ||
                       existDfs(i, j - 1, words, board, index + 1) ||
                       existDfs(i, j + 1, words, board, index + 1);
        // 还原数值
        board[i][j] = temp;
        return bool;
    }

    /**
     * 八皇后问题
     *
     * 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整
     * 个棋盘的那两条对角线。
     *
     *  注意：本题相对原题做了扩展
     *
     *  示例:
     *   输入：4
     *  输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
     *  解释: 4 皇后问题存在如下两个不同的解法。
     * [
     *  [".Q..",  // 解法 1
     *   "...Q",
     *   "Q...",
     *   "..Q."],
     *
     *  ["..Q.",  // 解法 2
     *   "Q...",
     *   "...Q",
     *   ".Q.."]
     * ]
     *
     *  Related Topics 回溯算法
     */
    // N皇后本质上就是一个枚举问题，和全排列、组合什么的一个道理。枚举问题都可以考虑使用DFS来解决
    // 每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上
    public List<List<String>> solveNQueens(int n) {
        // TODO 思路：
        // 1、先生成 n * n的二维数组，数组元素用 . 来填充
        // 2、每一轮循环，把Q 依次放在 0 ~ n的位置
        // 3、判断在每个位置的时候是否满足竖的 和 左 右对角线 没有其他的 Q。若不满足直接跳出 探索下一个位置
        // 4、找到满足的位置后继续探索下一层。
        // 5、重复 2-4 知道满足找到最后一行
        //

        // 定义二维数组
        char[][] chars = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(chars[i], '.');
        }
        // 定义结果集合
        List<List<String>> res = new ArrayList<>();
        solveNQueensDfs(chars, 0, res);
        return res;
    }

    private void solveNQueensDfs(char[][] chars, int rowIndex, List<List<String>> res) {
        int length = chars.length;
        // 当前row 等于矩阵行数
        if (length == rowIndex) {
            res.add(addList(chars, length));
            return;
        }
        // 判断位置是否符合要求
        for (int col = 0; col < length; col++) {
            if (checkQueen(chars, col, rowIndex, length)){
                // 当不存在皇后
                chars[rowIndex][col] = 'Q';
                // 递归
                solveNQueensDfs(chars, rowIndex + 1, res);
                // 将数据还原回去
                chars[rowIndex][col] = '.';
            }

        }

    }

    private boolean checkQueen(char[][] chars, int col, int rowIndex, int length) {

        //判断当前列有没有皇后,因为他是一行一行往下走的，
        //我们只需要检查走过的行数即可
        //当前坐标位置的上面有没有皇后
        for (int row = 0; row < rowIndex; row++) {
            // 竖向有Q
            if (chars[row][col] == 'Q'){
                return false;
            }
        }

        // TODO 方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，
        //  例如 (0,0)(0,0) 和 (3,3)(3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
        // 当前节点左上角方向
        for (int i = rowIndex - 1, j = col - 1; i >= 0 && j >= 0; i --, j --){
            if (chars[i][j] == 'Q') {
                return false;
            }
        }


        // TODO 方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，
        //  例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
        //
        // 判断当前坐标右上角是否有Q
        for (int i = rowIndex - 1, j = col + 1; i >= 0 && j < length; i --, j ++){
            if (chars[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    // 数组转换成list
    private List<String> addList(char[][] chars, int length) {
        List<String> position = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            position.add(String.valueOf(chars[i]));
        }
        return position;
    }

    /**
     * 堆箱子问题
     *
     * 堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最
     * 高的一堆箱子。箱堆的高度为每个箱子高度的总和。
     *  输入使用数组[wi, di, hi]表示每个箱子。
     *
     *  示例1:
     *   输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
     *  输出：6
     *
     *  示例2:
     *   输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
     *  输出：10
     *
     *  提示:
     *  箱子的数目不大于3000个。
     *
     *  Related Topics 动态规划 回溯算法
     */
    public int pileBox(int[][] box) {
        int len = box.length;
        int[] dp = new int[len];
        int res = 0;
        // 对箱子数组进行排序
        Arrays.sort(box, (o2, o1) -> {
            if (o1[0] != o2[0]) return o1[0] - o2[0];
            else if (o1[1] != o2[1]) return o1[1] - o2[1];
            else return o1[2] - o2[1];
        });
        for (int i = 0; i < len; i++) {
            dp[i] = box[i][2];
            for (int j = 0; j < i; j++) {
                if (box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2]){
                    dp[i] = Math.max(dp[i], box[j][2] + dp[i]);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }












}
